/*
 * @lc app=leetcode.cn id=37 lang=typescript
 *
 * [37] 解数独
 */

// @lc code=start
/**
 Do not return anything, modify board in-place instead.
 */

function solveSudoku(board: string[][]): void {
  // 存储每行已使用的数字
  const X: number[] = new Array(9).fill(0);
  // 存储每列已使用的数字
  const Y: number[] = new Array(9).fill(0);
  // 存储每个单元已使用的数字
  const Z: number[] = new Array(9).fill(0);
  /**
   * @description: 存储行、列、单元内的已使用的数字
   * @example
   * X[0]代表第一行，比如第一行如：["5","3",".",".","7",".",".",".","."]
   * X[0] = 10101000
   * 其中的1代表已经存在，具体代表的数字从低位到高位，从0开始计算。
   */
  const setCheck = (num: number, x: number, y: number): void => {
    X[x] ^= 1 << num;
    Y[y] ^= 1 << num;
    Z[((x / 3) >> 0) * 3 + ((y / 3) >> 0)] ^= 1 << num;
  };
  /**
   * @description: 检测数字是否已经在行、列或单元内
   */
  const check = (num: number, x: number, y: number): boolean => {
    if (X[x] & (1 << num)) return false;
    if (Y[y] & (1 << num)) return false;
    if (Z[((x / 3) >> 0) * 3 + ((y / 3) >> 0)] & (1 << num)) return false;
    return true;
  };
  /**
   * @description 初始化棋盘内已用的数据到存储中
   */
  const initBoard = (board: string[][]): void => {
    for (let i = 0; i < 9; i++) {
      for (let j = 0; j < 9; j++) {
        if (board[i][j] === '.') continue;
        setCheck(Number(board[i][j]), i, j);
      }
    }
  };

  /**
   * @description: 回溯
   */
  const backtrack = (board: string[][], index: number): boolean => {
    if (index === 81) return true;
    let x = (index / 9) >> 0;
    let y = index % 9;
    if (board[x][y] !== '.') return backtrack(board, index + 1);

    for (let i = 1; i <= 9; i++) {
      if (!check(i, x, y)) continue;
      setCheck(i, x, y);
      board[x][y] = String(i);
      if (backtrack(board, index + 1)) return true;
      setCheck(i, x, y);
      board[x][y] = '.';
    }
    return false;
  };

  initBoard(board);
  backtrack(board, 0);
}
// @lc code=end
